ICLR 2024 | 近似最优的最大损失函数量子优化算法
关键词：量子算法，量子询问复杂度，凸优化
导 读
本文是对发表在 ICLR 2024 顶级会议上的论文 Near-Optimal Quantum Algorithm for Minimizing the Maximal Loss 的详细解读。这项研究由北京大学信息科学技术学院本科生王昊、斯坦福大学博士生张辰逸和北京大学助理教授李彤阳合作完成，系统性的分析了最大损失函数的量子优化问题，提出了混合量子优化算法并证明了其近似最优性。
← 扫码跳转论文
论文地址：
https://arxiv.org/abs/2402.12745
01
背 景
本文考虑一个在最大损失函数上的优化问题。正式的讲，给定 个凸且 -Lipshitz的光滑函数 , 我们想要考虑在 上做优化，也即找到 从而使得 ，其中 是一个任意给定的准确度。这个问题在优化和机器学习中是非常重要的，尤其是监督学习。以支持向量机（SVM）为例，我们可以将 看做是当前的分类器对第 个数据点的负的间隔（margin）[1]，从而使得支持向量机的问题转化为了最大损失函数上的优化问题。作为一个快速发展的技术，量子计算有着比经典计算更快的速度。尽管量子算法在各种优化问题上已经展现了很大的加速，但是在对最大损失函数的优化问题上的应用还是较少的。本文的目标是通过系统的研究量子算法在最大损失函数的下界来解决这个问题。经典的方法在该问题上的最好复杂度为 [2]，使用一阶经典 Oracle。本文设计了一个使用量子零阶 Oracle 的混合量子算法来实现关于 的根号加速，达到 的时间复杂度，同时证明了任意混合量子算法在该问题上至少需要 次对 Oracle 的询问。
02
准 备
大致地讲，我们考虑的问题是在假设具有对一个量子零阶 Oracle 的访问的前提下，混合量子算法在背景中所描述的 上的优化效果。正式的讲，我们假设存在以下的一个量子 Oracle：
定义1
从而任何一个混合量子算法可以以
的形式以叠加态对该量子 Oracle 进行访问。该 Oracle 是量子零阶的，因为其的返回态中只包含了关于函数值，而没有关于函数梯度的信息。
本文中会用到量子计算中一个熟知的结论，即量子相比于经典在无结构搜索问题上 Grover 搜索算法提供的根号加速。我们简单介绍一下最简单的 Grover 搜索算法。给定 个无结构的元素，也即其之间无依赖，算法也事先对这 个元素没有先验知识，想要在其中考虑找到一个特定的元素 。该元素 在最简单的情况下由一个给定的量子 Oracle 指定。在经典情况下，我们最好的期望是进行随机采样后询问，这样做达到 成功概率的时间复杂度是 。而 Grover 搜索算法先构建一个叠加态 ，之后进行 次对给定量子 Oracle 的询问，使得给定元素对应的振幅每次询问都有大约 的增长。因此，在 的时间后，Grover 算法保证所需要搜索的元素的振幅是 的，再进行采样就能保证 的成功概率。本文用到的是该算法的最优性结论，即任何量子算法在无结构搜索问题上都需要至少 的复杂度来保证 的成功概率。
03
算法设计
本文的算法使用了在经典算法[2]中提出的框架。类似地，我们考虑实现一个球正规化优化 Oracle（ball regularized optimization oracle, BROO）。正式的讲，我们可以如下定义一个 BROO。
定义2
我们定义一个映射 是一个 上半径为 的球正规化优化 Oracle ( -BROO) 如果对于任意的点 ，正规化参数 和准确度 ，该映射返回 使得
那么实际上，使用经典算法[2]中的算法框架，我们便只需要考虑如何高效的实现一个 BROO。经典上，这个 BROO 是利用带有 Epoch 和投影的随机梯度下降实现[3,2]。因此，算法上我们考虑两个优化方向：
经典的一阶 Oracle 使用 Jordan 算法[4]可以由量子的零阶 Oracle 实现；
在随机梯度下降中的多次采样可以用量子实现根号加速(类似[5]) 。
04
下界证明
由于原文的下界证明较为繁琐，此处只介绍下界证明使用的 Hard Instance 以及证明的思路。类似经典中证明类似算法使用的 robust zero-chain[6]，我们此处考虑使用一个多函数的变体[2]：
定义3
一组函数 被称为一个 -robust -element zero-chain，当且仅当对任意 ，任意在 的临域中的 ，以及所有 ，都有
其中 的定义为
直观地讲，这里的 代表当前的输入 目前的进度，定义为 最右一位值大于给定的阈值 所在的坐标号。相对的，我们所使用的 hard instance 的直觉则是要使得每一次询问时 的进度能增加的概率很小，期望上需要足够长的时间才能使得下一个坐标不为0（通过梯度等）。同时，只有 大于一定的值， 才能是满足最优的点。这里我们的方法是为不同的进度 指定一个对应的 ，使得只有对这个 进行询问才能得到有关下一个坐标的梯度信息。如此，我们可以粗略判断，在每一个坐标上任何经典算法都期望需要 的时间，而混合算法由于可以用 Grover 算法加速无结构搜索，只需要 的时间。 也是量子算法所至少需要的在无结构搜索问题上达到 误差的时间。当然，如果直接认为 是算法的输入， 的顺序也不变，那完全可以打表。因此我们考虑的是如上的 hard instance 做一个随机旋转 ， 的下标也做一个随机排列的随机化 hard instance。
证明的细节比较繁琐，大概的思路是先使用我们上面的直觉构造一个 hybrid argument，将一个算法中调用的量子 Oracle 中有关高坐标的信息部分去除，再用常规的概率论手段证明 hybrid argument 中 Oracle 完全替换后的算法以极小的可能性能“猜”到满足准确度 的最小值的位置。具体的证明见论文。
05
结 论
本文在使用量子算法优化由凸且 Lipshitz 的光滑函数组成的最大损失函数 这个问题上系统性的做了研究。在假设具有零阶量子算法的基础上，设计了一个新的量子算法，在该问题的时间复杂度上从 加速至了 ，实现了根号加速。同时，通过证明任何混合量子算法在该问题上的下界为 证明了算法的近似最优性。通过设计近似最优的量子算法来解决这个问题，本文有助于推动对量子优化技术的理解以及其在实际场景中的应用。
参考文献
[1] V. N. Vapnik, "An overview of statistical learning theory," IEEE Transactions on Neural Networks, vol. 10, no. 5, pp. 988–999, 1999.
[2] Y. Carmon, A. Jambulapati, Y. Jin, and A. Sidford, "Thinking inside the ball: Near-optimal minimization of the maximal loss," in Conference on Learning Theory, pp. 866–882, PMLR, 2021.
[3] E. Hazan and S. Kale, "Beyond the Regret Minimization Barrier: Optimal Algorithms for Stochastic Strongly-Convex Optimization," Journal of Machine Learning Research, vol. 15, no. 71, pp. 2489–2512, 2014.
[4] S. P. Jordan, "Fast quantum algorithm for numerical gradient estimation," Physical Review Letters, vol. 95, no. 5, p. 050501, 2005.
[5] Y. Hamoudi, "Preparing many copies of a quantum state in the blackbox model," Physical Review A, vol. 105, no. 6, p. 062440, 2022.
[6] Y. Carmon, J. C. Duchi, O. Hinder, and A. Sidford, "Lower bounds for finding stationary points I," Mathematical Programming, vol. 184, no. 1, pp. 71–120, 2020.
图文 | 王昊
PKU QUARK Lab
关于量子算法实验室
量子算法实验室 QUARK Lab (Laboratory for Quantum Algorithms: Theory and Practice) 由李彤阳博士于2021年创立。该实验室专注于研究量子计算机上的算法，主要探讨机器学习、优化、统计学、数论、图论等方向的量子算法及其相对于经典计算的量子加速；也包括近期 NISQ (Noisy, Intermediate-Scale Quantum Computers) 量子计算机上的量子算法。
实验室新闻：#PKU QUARK
实验室公众号：
课题组近期动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点击“阅读原文”转论文链接